package code.mySpecializedTraining;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/22
 * @description
 */
public class Graph {
    // 3123. 最短路径中的边（查询节点所有最短路径 → dijkstra+前驱边）
    public boolean[] findAnswer(int n, int[][] edges) {
        // 构建图
        int m = edges.length;
        List<PathEdge>[] graphEdges = new List[n];
        for (int i = 0; i < n; i++)
            graphEdges[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            graphEdges[edges[i][0]].add(new PathEdge(edges[i][1], edges[i][2], i));
            graphEdges[edges[i][1]].add(new PathEdge(edges[i][0], edges[i][2], i));
        }
        // dijkstra
        List<PathEdge>[] prev = new List[n]; // prev[i]表示从0到达节点i最短路径的所有前驱节点
        for (int i = 0; i < n; i++)
            prev[i] = new ArrayList<>();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        PriorityQueue<PathNode> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.dist, o2.dist));
        queue.offer(new PathNode(0, 0));
        while (!queue.isEmpty()) {
            PathNode node = queue.poll();
            int nodeDist = node.dist;
            int nodeIdx = node.idx;
            if (nodeDist > dist[nodeIdx])
                continue;
            for (PathEdge edge : graphEdges[nodeIdx]) {
                int newDist = nodeDist + edge.len;
                int oldDist = dist[edge.idx];
                if (newDist < oldDist) {
                    dist[edge.idx] = newDist;
                    prev[edge.idx].clear();
                    prev[edge.idx].add(new PathEdge(nodeIdx, edge.len, edge.i));
                    queue.offer(new PathNode(edge.idx, newDist));
                } else if (newDist == oldDist) {
                    prev[edge.idx].add(new PathEdge(nodeIdx, edge.len, edge.i));
                }
            }
        }
        // dfs获得答案
        boolean[] ans = new boolean[m];
        boolean[] visited = new boolean[n];
        getAnsDFS(ans, n - 1, visited, prev);
        return ans;
    }

    private void getAnsDFS(boolean[] ans, int node, boolean[] visited, List<PathEdge>[] prev) {
        if (visited[node])
            return;
        visited[node] = true;
        for (PathEdge edge : prev[node]) {
            ans[edge.i] = true;
            getAnsDFS(ans, edge.idx, visited, prev);
        }
    }

    static class PathEdge {
        public PathEdge(int idx, int len, int i) {
            this.idx = idx;
            this.len = len;
            this.i = i;
        }
        int idx;
        int len;
        int i; // 边在数组edges中的下标
    }

    static class PathNode {
        public PathNode(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
        int idx;
        int dist;
    }

    // 399. 除法求值（查询节点到节点的距离 → 图的BFS）

    // 图+BFS。本题并不是求最短路，查询的过程只是遍历图即可。
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 为每个节点编号
        Map<String, Integer> map = new HashMap<>();
        int m = equations.size();
        int idx = 0;
        for (List<String> equation : equations) {
            String a1 = equation.get(0);
            String a2 = equation.get(1);
            if (!map.containsKey(a1))
                map.put(a1, idx++);
            if (!map.containsKey(a2))
                map.put(a2, idx++);
        }
        // 构图
        List<CalcEquationEdge>[] edges = new List[idx];
        for (int i = 0; i < idx; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int idx1 = map.get(equations.get(i).get(0));
            int idx2 = map.get(equations.get(i).get(1));
            double val = values[i];
            edges[idx1].add(new CalcEquationEdge(idx2, val));
            edges[idx2].add(new CalcEquationEdge(idx1, 1 / val));
        }
        // 查询
        int qSize = queries.size();
        double[] ans = new double[qSize];
        for (int i = 0; i < qSize; i++) {
            List<String> list = queries.get(i);
            // 没有这个点，默认 -1.0
            if (!map.containsKey(list.get(0)) || !map.containsKey(list.get(1))) {
                ans[i] = -1.0;
                continue;
            }
            int idxStart = map.get(list.get(0)), idxEnd = map.get(list.get(1));
            // BFS graph
            double[] temp = new double[idx];
            Arrays.fill(temp, -1.0);
            temp[idxStart] = 1.0;
            Deque<Integer> queue = new ArrayDeque<>();
            queue.offer(idxStart);
            while (!queue.isEmpty()) {
                int nowIdx = queue.poll();
                for (CalcEquationEdge edge : edges[nowIdx]) {
                    // edge.idx是nowIdx的邻接点，如果他不是-1了，代表已经遍历过了
                    if (temp[edge.idx] != -1.0)
                        continue;
                    temp[edge.idx] = edge.len * temp[nowIdx];
                    queue.offer(edge.idx);
                }
            }
            ans[i] = temp[idxEnd];
        }
        return ans;
    }

    static class CalcEquationEdge {
        int idx;
        double len;
        public CalcEquationEdge(int idx, double len) {
            this.idx = idx;
            this.len = len;
        }
    }

    // 743. 网络延迟时间（查询节点的最短距离 → dijkstra）
    public int networkDelayTime(int[][] times, int n, int k) {
        // 构图
        List<NetEdge>[] edges = new List[n + 1];
        for (int i = 1; i <= n; i++)
            edges[i] = new ArrayList<>();
        for (int[] time : times)
            edges[time[0]].add(new NetEdge(time[1], time[2]));
        // dijkstra
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[0], o2[0]));
        queue.offer(new int[]{k, 0});
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowIdx = now[0];
            int nowDist = now[1];
            if (nowDist > dist[nowIdx])
                continue;
            // 遍历nowIdx的所有临边
            for (NetEdge edge : edges[nowIdx]) {
                if (edge.time + nowDist < dist[edge.idx]) {
                    dist[edge.idx] = edge.time + nowDist;
                    queue.offer(new int[]{edge.idx, dist[edge.idx]});
                }
            }
        }
        // 如果有无法到达的，返回-1
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dist[i]);
        }
        if (max == Integer.MAX_VALUE)
            return -1;
        return max;
    }

    static class NetEdge {
        int idx;
        int time;
        public NetEdge(int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
    }

    // 787. K 站中转内最便宜的航班（在指定步数内，查询节点的最短距离 → dijkstra+步数限制）
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 构建图
        List<FlyEdge>[] edges = new List[n];
        for (int i = 0; i < n; i++)
            edges[i] = new ArrayList<>();
        for (int[] flight : flights)
            edges[flight[0]].add(new FlyEdge(flight[1], flight[2]));
        // dijkstra
        int[] dist = new int[n];
        int[] transTimes = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(transTimes, Integer.MAX_VALUE);
        dist[src] = 0;
        transTimes[src] = 0;
        PriorityQueue<FlyNode> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.dist, o2.dist));
        queue.offer(new FlyNode(src, 0,0));
        while (!queue.isEmpty()) {
            FlyNode node = queue.poll();
            // 如果超出转机次数，continue
            if (node.transTimes > k) continue;
            // 如果第一次访问到了目标节点，说明一定是最优答案。因为超出转机次数访问不到目标节点，能访问到，第一次一定是最短的。
            if (node.idx == dst) return node.dist;
            // 访问这个node的临边
            for (FlyEdge edge : edges[node.idx]) {
                int newDist = node.dist + edge.price;
                int newSpend = node.transTimes + (edge.idx == dst ? 0 : 1);
                // 如果花费更少，更新
                if (newDist < dist[edge.idx]) {
                    dist[edge.idx] = newDist;
                    transTimes[edge.idx] = newSpend;
                }
                // 如果【又贵，中转又多】
                if (newDist > dist[edge.idx] && newSpend > transTimes[edge.idx])
                    continue;
                // 【贵，但中转少】【便宜，但中转多】这两种情况会走到这一步，考虑这两种情况
                queue.offer(new FlyNode(edge.idx, newDist, newSpend));
            }
        }
        return -1;
    }

    static class FlyEdge {
        int idx;
        int price;
        public FlyEdge(int idx, int price) {
            this.idx = idx;
            this.price = price;
        }
    }

    static class FlyNode {
        int idx;
        int dist;
        int transTimes;
        public FlyNode(int idx, int dist, int transTimes) {
            this.idx = idx;
            this.dist = dist;
            this.transTimes = transTimes;
        }
    }

    // 787. K 站中转内最便宜的航班（bellman ford）
    public int findCheapestPrice_bellman_ford(int n, int[][] flights, int src, int dst, int k) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        // bellman ford 算法，进行 |V - 1| 次循环，松弛所有边 |V - 1| 次，得到最多包含 |V| 个节点的路线
        // 这里中转限定为 K 次，所以进行 |K + 1| 次循环，得到最长包含 |K + 2| 个节点的路线，同时防止一次多次更新，需要 temp dist
        for (int i = 0; i <= k; i++) {
            int[] tempDist = Arrays.copyOf(dist, n);
            for (int[] flight : flights) {
                if (dist[flight[0]] != Integer.MAX_VALUE && dist[flight[0]] + flight[2] < tempDist[flight[1]])
                    tempDist[flight[1]] = dist[flight[0]] + flight[2];
            }
            dist = tempDist;
        }
        if (dist[dst] == Integer.MAX_VALUE)
            return -1;
        return dist[dst];
    }

    // 1334. 阈值距离内邻居最少的城市（查询所有节点的最短距离 → floyd）
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int max = Integer.MAX_VALUE / 2;
        // 初始化
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], max);
            dist[i][i] = 0;
        }
        for (int[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
            dist[edge[1]][edge[0]] = edge[2];
        }
        // floyd
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] < max && dist[k][j] < max)
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        // find answer
        int[] ans = new int[n]; // 阈值范围内能到达的城市数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (dist[i][j] <= distanceThreshold)
                    ans[i]++;
            }
        }
        // get ans
        int min = Arrays.stream(ans).min().getAsInt();
        int city = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (ans[i] == min) {
                city = i;
                break;
            }
        }
        return city;
    }

    // 1514. 概率最大的路径（求节点的最短距离-其实是求最大值，都一样 → dijkstra把加法改为乘法找最大值）
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        // 构建图
        int m = edges.length;
        List<List<MaxEdge>> graphEdges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            graphEdges.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int n1 = edges[i][0], n2 = edges[i][1];
            double prob = succProb[i];
            graphEdges.get(n1).add(new MaxEdge(n2, prob));
            graphEdges.get(n2).add(new MaxEdge(n1, prob));
        }
        // dijkstra
        double[] probs = new double[n];
        Arrays.fill(probs, 0.0);
        probs[start_node] = 1;
        PriorityQueue<MaxNode> priorityQueue = new PriorityQueue<>((o1, o2) -> Double.compare(o2.prob, o1.prob));
        priorityQueue.offer(new MaxNode(start_node, 1.0));
        while (!priorityQueue.isEmpty()) {
            MaxNode node = priorityQueue.poll();
            int idx = node.idx;
            double prob = node.prob;
            if (prob < probs[idx])
                continue;
            for (MaxEdge edge : graphEdges.get(idx)) {
                double newProb = prob * edge.prob;
                double oldProb = probs[edge.idx];
                if (newProb > oldProb) {
                    probs[edge.idx] = newProb;
                    priorityQueue.offer(new MaxNode(edge.idx, newProb));
                }
            }
        }

        return probs[end_node];
    }

    static class MaxEdge {
        int idx;
        double prob;
        public MaxEdge(int idx, double prob) {
            this.idx = idx;
            this.prob = prob;
        }
    }

    static class MaxNode {
        int idx;
        double prob;

        public MaxNode(int idx, double prob) {
            this.idx = idx;
            this.prob = prob;
        }
    }

    // 1786. 从第一个节点出发到最后一个节点的受限路径数
    public int countRestrictedPaths(int n, int[][] edges) {
        // 先求每个节点蓝色括号里的「到第n个节点的最短路径长度」，再根据这个条件找到所有满足的路径
        // 1. 需要找所有节点到n的最短距离，也就是n到所有节点的最短距离，dijkstra！
        // 1.1 构图
        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++)
            graph[i] = new ArrayList<>();
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
            graph[edge[1]].add(new int[]{edge[0], edge[2]});
        }
        // 1.2 dijkstra
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        pq.offer(new int[]{n, 0});
        dist[n] = 0;
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            int nowIdx = now[0];
            int nowDist = now[1];
            if (nowDist < dist[nowIdx])
                continue;
            for (int[] e : graph[nowIdx]) {
                int nextIdx = e[0];
                int len = e[1];
                if (nowDist + len < dist[nextIdx]) {
                    dist[nextIdx] = nowDist + len;
                    pq.offer(new int[]{nextIdx, dist[nextIdx]});
                }
            }
        }
        // 1.3 得到每个节点到n的最短距离
        int[] distanceToLastNode = dist;
        // 2. DFS + 记忆化 找到所有满足的路径总数
        int[] remember = new int[n + 1];
        Arrays.fill(remember, -1);
        return dfs_remember(1, n, remember, graph, distanceToLastNode);
    }

    private int dfs_remember(int u, int n, int[] remember, List<int[]>[] graph, int[] distanceToLastNode) {
        // 遍历到目标节点，返回1
        if (u == n)
            return 1;
        // 记忆化，如果遍历过这个节点，直接返回结果
        if (remember[u] != -1)
            return remember[u];
        // 遍历这个点所有的临边，确定他的答案
        int ans = 0;
        for (int[] e : graph[u]) {
            if (distanceToLastNode[u] <= distanceToLastNode[e[0]])
                continue;
            ans = (ans + dfs_remember(e[0], n, remember, graph, distanceToLastNode)) % 1000000007;
        }
        remember[u] = ans;
        return remember[u];
    }

    // 1976. 到达目的地的方案数
    public int countPaths(int n, int[][] roads) {
        // graph[i] 表示节点i的所有临边 int[] 的 List<int[]>
        // 边 int[] = {目标节点, 长度}
        // 1. 构图
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for (int[] road : roads) {
            graph[road[0]].add(new int[]{road[1], road[2]});
            graph[road[1]].add(new int[]{road[0], road[2]});
        }
        // 2. 准备 dijkstra
        // dist 数组
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0L;
        // 记录路径数的数组
        int[] ways = new int[n];
        ways[0] = 1;
        // 优先队列
        PriorityQueue<PQNode> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1.dist, o2.dist));
        pq.offer(new PQNode(0, 0L));
        // 3. dijkstra
        while (!pq.isEmpty()) {
            PQNode now = pq.poll();
            if (now.dist > dist[now.idx])
                continue;
            for (int[] edge : graph[now.idx]) {
                if (now.dist + edge[1] < dist[edge[0]]) {
                    dist[edge[0]] = now.dist + edge[1];
                    ways[edge[0]] = ways[now.idx];
                    pq.offer(new PQNode(edge[0], dist[edge[0]]));
                } else if (now.dist + edge[1] == dist[edge[0]]) {
                    ways[edge[0]] = (ways[edge[0]] + ways[now.idx]) % 1000000007;
                }
            }
        }
        return ways[n - 1];
    }

    class PQNode {
        int idx;
        long dist;
        public PQNode (int idx, long dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }

    // 2662. 前往目标的最小代价
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        // 1. 找到所有点和边，用 hash 的方法建图
        // 找到所有点
        Set<Long> v = new HashSet<>();
        long start_idx = getIdx(start[0], start[1]);
        long end_idx = getIdx(target[0], target[1]);
        v.add(start_idx);
        v.add(end_idx);
        for (int[] sRoad : specialRoads) {
            v.add(getIdx(sRoad[0], sRoad[1]));
            v.add(getIdx(sRoad[2], sRoad[3]));
        }
        // 建图
        Map<Long, List<long[]>> graph = new HashMap<>();
        for (long i : v) {
            for (long j : v) {
                long dis = getDistance(i, j);
                addEdge(graph, dis, i, j);
                addEdge(graph, dis, j, i);
            }
        }
        for (int[] sRoad : specialRoads) {
            addEdge(graph, sRoad[4], getIdx(sRoad[0], sRoad[1]), getIdx(sRoad[2], sRoad[3]));
        }
        // 2. dijkstra
        Map<Long, Long> dist = new HashMap<>();
        PriorityQueue<long[]> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1[1], o2[1]));
        dist.put(getIdx(start[0], start[1]), 0L);
        pq.offer(new long[]{start_idx, 0L});
        while (!pq.isEmpty()) {
            long[] now = pq.poll();
            long nowDist = now[1];
            long nowIdx = now[0];
            if (dist.containsKey(nowIdx) && nowDist > dist.get(nowIdx))
                continue;
            // 第一次遇见 target 就是答案（这就是Dijkstra！）
            if (nowIdx == end_idx)
                return (int) nowDist;
            // dijkstra 遍历当前的邻边
            for (long[] neighbor : graph.getOrDefault(nowIdx, new ArrayList<>())) {
                long nextIdx = neighbor[0];
                long len = neighbor[1];
                if (nowDist + len < dist.getOrDefault(nextIdx, Long.MAX_VALUE)) {
                    dist.put(nextIdx, nowDist + len);
                    pq.offer(new long[]{nextIdx, nowDist + len});
                }
            }
        }

        return dist.getOrDefault(end_idx, getDistance(start_idx, end_idx)).intValue();
    }

    // 添加边
    private void addEdge(Map<Long, List<long[]>> graph, long dis, long i, long j) {
        List<long[]> list = graph.getOrDefault(i, new ArrayList<>());
        list.add(new long[]{j, dis});
        graph.put(i, list);
    }

    // 把 x 和 y 这两个 int(32bit) 压缩到 long(64bit) 中
    private long getIdx(int x, int y) {
        return ((long) x) << 32 | (long) y;
    }

    // 把 long 还原为 x y
    private int[] getXY(long l) {
        return new int[]{(int) (l >> 32), (int) (l & Integer.MAX_VALUE)};
    }

    // 求 pos1 到 pos2 的距离
    private long getDistance(long l1, long l2) {
        int[] pos1 = getXY(l1);
        int[] pos2 = getXY(l2);
        return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
    }
}
